package com.rui.study.algorithm.P_动态规划_莱文斯坦距离;

import java.util.Random;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-04 11:05
 **/
public class Solution3动态规划_状态转移表法 {

    public int findEdit(char[] a, char[] b) {
        int m = a.length, n = b.length;
        Integer[][] edist = new Integer[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j ==0) {
                    if (a[i] == b[j]) edist[i][j] = 0;
                    else edist[i][j] = 1;
                    continue;
                }

                if (i == 0) {
                    if (a[i] == b[j]) edist[i][j] = j;
                    else edist[i][j] = edist[i][j-1] + 1;
                    continue;
                }

                if (j == 0) {
                    if (a[i] == b[j]) edist[i][j] = i;
                    else edist[i][j] = edist[i-1][j] + 1;
                    continue;
                }

                if (a[i] == b[j]) {
                    edist[i][j] = minEdit(edist[i-1][j] + 1, edist[i][j-1] + 1, edist[i-1][j-1]);
                } else {
                    edist[i][j] = minEdit(edist[i-1][j] + 1, edist[i][j-1] + 1, edist[i-1][j-1] + 1);
                }
            }
        }
        return edist[m-1][n-1];

    }

    private int minEdit(int x, int y, int z) {
        int min = Integer.MAX_VALUE;
        if (x < min) min = x;
        if (y < min) min = y;
        if (z < min) min = z;
        return min;
    }

    public static void main(String[] args) {
//        char[] a = "mtacnu".toCharArray();
//        char[] b = "mitcmu".toCharArray();
        int len = 500, ratio = 4;
        char[] a = new char[len];
        char[] b = new char[len];
        Random r1 = new Random(31);
        Random r2 = new Random(31);
        Random r3 = new Random(7);
        StringBuffer bbuf = new StringBuffer();
        for (int i = 0; i < len; i++) {
            a[i] = (char) (97 + r1.nextInt(26));
            char bc = (char) (97 + r2.nextInt(26));
            if (i % ratio != 0) {
                bbuf.append(bc);
            } else {
                bbuf.append((char) (97 + r3.nextInt(26)));
            }
        }
        b = bbuf.toString().toCharArray();
        System.out.println("a: " + String.valueOf(a));
        System.out.println("b: " + String.valueOf(b));
        Solution3动态规划_状态转移表法 solution1回溯法 = new Solution3动态规划_状态转移表法();
        long start = System.currentTimeMillis();
        int minEdit = solution1回溯法.findEdit(a, b);
        long end = System.currentTimeMillis();
        System.out.println("最小编辑次数：" + minEdit + ", 用时：[" + (end - start) + "ms]");
    }
}
